/*https://leetcode.cn/problems/kth-missing-positive-number/submissions/562480311/*/

class Solution {
public:
    int findKthPositive(vector<int>& arr, int k) {
        //对于每个元素a[i]，我们都可以确定,到当前元素为止，所缺失的元素数量为a[i]-i-1,设为b[i]
        //如何判断该题可使用二分
        //由于b[i]是随着i非严格递增的，即函数在区间内单调，满足二分的条件
        //目的：找第一个大于等于k的b[i]————实为下界查找
        int l = 0,r = arr.size()-1;
        while(l <= r){
            int mid = l + (r-l)/2;
            if(arr[mid]-mid-1 >= k){
                r = mid-1;
            }else{
                l = mid+1;
            }
        }
        //此时，l 指向的位置是第一个“缺失元素数量”大于或等于 k - (l - 0) 的位置（因为我们已经越过了所有缺失元素数量小于 k 的位置）。
    return l+k;
    }
};